const MAX = Infinity;
let graph = [
  [0, 4, 6, 6, MAX, MAX, MAX],

  [0, 0, 1, MAX, 7, MAX, MAX],

  [MAX, MAX, 0, MAX, 6, 4, MAX],

  [MAX, MAX, 2, 0, MAX, 5, MAX],

  [MAX, MAX, MAX, MAX, 0, MAX, 6],

  [MAX, MAX, MAX, MAX, 1, 0, 8],

  [MAX, MAX, MAX, MAX, MAX, MAX, 0]

];

let vertexNum = graph.length;
//console.log(vertexNum);

let s = [], // 记录已添加的点
    dist = [], // 记录源点到 i 的最短路径
    path = []; // 到达i 的最短路径需要经过 path[i]
    
let startV = 0; // 设源点为 V0

function init(graph, startV) {
  for(let i = 0; i < graph[startV].length; i++) {
    s[i] = 0;
  }
  s[startV] = 1; // s 数组中的元素 记录已找到最短路径的元素，s[0] = 1 即表示V0已找到最短路径
  for(let i = 0; i < graph[startV].length; i++) {
    dist[i] = graph[startV][i];
    if(dist[i] != MAX) {
      path[i] = startV;
    } else {
      path[i] = -1; // -1 表示源点 到Vi 路径不可达 
    }
  }
}

init(graph, startV);
console.log(s);
//console.log(dist);
//console.log(path);


function findMinDist(dist, s) {
  let minWeight = MAX;
  let i;
  let min;
  for(i = 0; i < dist.length; i++) {
    if(s[i] == 0) {
      if(dist[i] < minWeight) {
        minWeight = dist[i];
        min = i;
      }
    }
  }
  
  return min;
}


//let min = findMinDist(dist, s);
//console.log(min);

function Dijkstra(graph, startV, s, dist, path) {
  let num = 1,
      vertexNum = graph.length;
  while(num < vertexNum) {
    let min = findMinDist(dist, s);
    s[min] = 1;
    for(i = 0; i < vertexNum; i++) {
      if(s[i] == 0 && (dist[i] > dist[min] + graph[min][i])){
        dist[i] = dist[min] + graph[min][i];
        path[i] = min;
      }
    }
    
    num++;
  }
  
  displayPath(path, 5, startV);
}

// 参数i， 终点
function displayPath(path, i, startV) {
  let stack = [];
  while(i != startV) {
    stack.push(i);
    i = path[i];
  }
  stack.push(startV);
  
  let str = ''; // 直接let， 不赋值，打印结果显示undefined
  while(stack.length > 0) {
    str += stack.pop() + ' ';
  }
  console.log(str);
  
}

Dijkstra(graph, startV, s, dist, path);